package com.yulongtian.interviewWorks.day20221116;

import java.util.HashSet;

/**
 * https://leetcode.cn/problems/permutation-ii-lcci/?favorite=xb9lfcwi
 * 可
 *
 * @author yulongTian
 * @create 2022-11-16 10:50
 */
public class Test02 {
    public static void main(String[] args) {

    }

    public static String[] permutation(String s) {
        if (s.length() == 1) {
            return new String[]{s};
        }
        HashSet<String> resSet = new HashSet<>();
        char[] chars = s.toCharArray();
        dfs(resSet, 0, chars);
//        System.out.println(resSet);

        return resSet.toArray(new String[0]);
    }

    public static void dfs(HashSet<String> resSet, int cur_index, char[] chars) {
        for (int i = cur_index; i < chars.length; i++) {
            swap(chars, cur_index, i);
            //转换字符串
            StringBuilder temp = new StringBuilder();
            for (char aChar : chars) {
                temp.append(aChar);
            }
            resSet.add(temp.toString());
            //dfs
            dfs(resSet, cur_index + 1, chars);
            swap(chars, cur_index, i);
        }
    }

    //交换
    public static void swap(char[] chars, int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }
}
